package com.banmao.algorithm.No1To100.No21;

import lombok.Data;

public class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode head = new ListNode();
        ListNode cur = head;
        ListNode left = list1, right = list2;

        while (left != null || right != null) {
            if(left != null && right != null) {
                if(left.val > right.val) {
                    cur.next = right;
                    right = right.next;
                } else {
                    cur.next = left;
                    left = left.next;
                }
            } else {
                if(left != null) {
                    cur.next = left;
                    left = left.next;
                } else {
                    cur.next = right;
                    right = right.next;
                }
            }
            cur = cur.next;
        }

        return head.next;
    }

}

@Data
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
